#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#include "uthash.h"

#include <iso646.h>

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
};
typedef struct TreeNode tree_node, *tree_node_ptr;

int maxPathSum(struct TreeNode* root);

int dfs_max(tree_node_ptr root);

int main()
{
	return 0;
}

int res;
int maxPathSum(struct TreeNode* root)
{
	res = INT_MIN;
	dfs_max(root);
	return res;
}

int dfs_max(tree_node_ptr root)
{
	if (!root) return 0;
	int left_max = dfs_max(root->left),
		right_max = dfs_max(root->right), cur;
	res = fmax(res, (cur = left_max + right_max + root->val));
	return fmax(cur - fmin(left_max, right_max), 0);
}
